\documentclass[a4paper,10pt]{article}
\usepackage[margin=2.5cm]{geometry}
\usepackage{amsmath}
\usepackage{amssymb,amsfonts,amsthm}
\usepackage[english]{babel}
\usepackage{graphicx}
\usepackage{cite}

%\linespread{1.1}

\newtheoremstyle{plain}{5pt}{5pt}{\normalfont\normalsize\slshape}{0pt}{\normalfont\normalsize\bfseries}{.}{3pt}{}
\newtheoremstyle{definition}{5pt}{5pt}{\normalfont\normalsize\rmfamily}{0pt}{\normalfont\normalsize\bfseries}{.}{3pt}{}

\theoremstyle{definition}
\newtheorem*{example}{Example}
\newtheorem{algorithm}{Algorithm}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{Obs}{Observation}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{Prop}{Proposition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{conjecture}{Conjecture}[section]

\renewcommand{\thesection}{\arabic{section}.\hskip-0.7em}
%\renewcommand{\thefigure}{\thesection\hskip0.7em\arabic{figure}}
%\renewcommand{\thetable}{\thesection\hskip0.7em\arabic{table}}
\renewcommand{\thesubsection}{\thesection\hskip0.7em\arabic{subsection}.\!\!\!}%

\renewcommand{\thealgorithm}{\thesection\hskip0.7em\arabic{algorithm}}
\renewcommand{\theremark}{\thesection\hskip0.7em\arabic{remark}}
\renewcommand{\thetheorem}{\thesection\hskip0.7em\arabic{theorem}}
\renewcommand{\theProp}{\thesection\hskip0.7em\arabic{Prop}}
\renewcommand{\thelemma}{\thesection\hskip0.7em\arabic{lemma}}
\renewcommand{\thecorollary}{\thesection\hskip0.7em\arabic{corollary}}
\renewcommand{\theconjecture}{\thesection\hskip0.7em\arabic{conjecture}}

\begin{document}
\title{On Abelian Repetition Threshold}
\author{Alexey V. Samsonov, Arseny M. Shur\\ Ural State University\\ Ekaterinburg, Russia}
\date{}
\maketitle
\begin{abstract} 
We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.\,e. a numerical value separating $k$-avoidable and $k$-unavoidable Abelian powers for each size $k$ of the alphabet. We prove lower bounds for the Abelian repetion threshold for large alphabets and all definitions of Abelian fractional power. We develop a method estimating the exponential growth rate of Abelian-power-free languages. Using this method, we get non-trivial lower bounds for Abelian repetition threshold for small alphabets. We suggest that some of the obtained bounds are the exact values of Abelian repetition threshold.
\end{abstract}

\section*{Introduction}

The study of avoidable powers of words has more than a centennial history since the paper by Thue \cite{Th}. If $w$ is a word, $|w|$ is its length, $\beta>1$ is a number, then $w^{\beta}$ is a unique prefix $v$ of the infinite word $www\ldots$, whose length satisfies the conditions $|v|/|w|\ge\beta$, $(|v|{-}1)/|w|<\beta$. A word $u$ is \textit{$\beta$-free}, if none of its factors, including $u$ itself, is a $\beta$-power. A $\beta$-power is said to be \textit{$k$-avoidable} if there are infinitely many $\beta$-free words (or, equivalently, an infinite $\beta$-free word) over the $k$-letter alphabet, and \textit{$k$-unavoidable} otherwise.

For any $k$-letter alphabet ($k\ge2$), the \textit{repetition threshold} is the number $RT(k)$ which separates $k$-unavoidable and $k$-avoidable powers of words. Famous Dejean's conjecture \cite{Dej} (proven in \cite{Car, CR, Rao}) states that $RT(3)=7/4$, $RT(4)=7/5$, and $RT(k)=k/(k{-}1)$ otherwise.

Abelian powers of words were first considered in \cite{Erd}.
The word $w_1w_2\ldots w_n$ is an \textit{Abelian $n$-th power}, if each of the words $w_2,\ldots,w_n$ is an anagram of $w_1$.
The avoidability of Abelian integral powers is well studied (\cite{ACR, Car1, Cur, Dek, Ker}). In contrast with the usual powers, there are several ways to generalize the notion of Abelian power to fractional exponents. We define weak, semistrong and strong Abelian fractional powers and then work with all three definitions. Once a definition of Abelian fractional power is chosen, Abelian repetition threshold can be defined in the same way as the ``usual'' repetition threshold. We study the values of Abelian repetition threshold for all alphabets and three suggested definitions.

\section*{Definitons}

Let $\Sigma=\{1,\ldots,k\}$ be an alphabet and $w\in\Sigma^*$ be an arbitrary $k$-ary word. The Parikh vector $\vec p(w)$ is the vector of length $k$ whose $i$th component equals the number of occurrences of the letter $i$ in $w$, for any $i=1,\ldots,k$. If $v\in\Sigma^*$, then the notation $\vec p(w) \le \vec p(v)$ means that the $i$th component of $\vec p(w)$ is not greater than the $i$th component of $\vec p(v)$, for any $i=1,\ldots,k$.

Let $m \ge 2$ be an integer. An \textit{Abelian m-power} is a word of the form $w_{1}w_{2} \ldots w_{m}$, where $w_{i}$ is an anagram of $w_{1}$ for $2 \le i \le m$, or $\vec p(w_1)=\ldots=\vec p(w_m)$. Now we extend this definition to the rational numbers in the range $(1,\infty)$. Let $\beta > 1$,  $|w_1|=q$, $m=\lfloor\beta\rfloor$, $t=\lceil\{\beta\}q\rceil$, where $\{\beta\}$ stands for the fractional part of $\beta$. Consider a word of the form $w = w_{1} \ldots w_{m}v$, where $w_{1} \ldots w_{m}$ is an abelian $m$-power and $|v| = t$. The terms \textit{root} and \textit{tail} denote the words $w_{1}$ and $v$ respectively. We consider three different restrictions upon the Parikh vector of the tail, thus obtaining three definitions of Abelian fractional power. Let $\mathrm{pref}(u, l)$ be the prefix of length $l$ of the word $u$.

A \textit{weak Abelian $\beta$-power} is a word $w$ of the form described above such that $\vec p(v)\le\vec p(w_1)$. That is, the tail is a prefix of an anagram of the root.

A \textit{strong Abelian $\beta$-power} is a word $w$ of the form described above such that $\vec p(v)=\vec p(\mathrm{pref}(w_1,t))$. That is, the tail is an anagram of a prefix of the root.

A \textit{semistrong Abelian $\beta$-power} is a word $w$ of the form described above such that $\vec p(v)\le\!\!\bigvee\limits_{i=\overline{1,m}}\!\!\vec p(\mathrm{pref}(w_i,t))$, where $\bigvee$ is the operation of taking maximum componentwise.

\begin{example}
The word $abc\,cba\,ac$ is a semistrong and a weak Abelian $(8/3)$-power, but not a strong Abelian $(8/3)$-power, because $ac$ is not a permutation of $ab$. The word $abcaa$ is not even a weak Abelian $(5/3)$-power,
but is a strong, semistrong and weak Abelian $(5/4)$-power.
\end{example}

\textit{Abelian exponent} of a word $w$ is the maximal rational number $\beta$ such that $w$ is an Abelian $\beta$-power.
A word $w$ is \textit{Abelian-$\beta$-free} if all its factors have Abelian exponents less than $\beta$. By \textit{Abelian-$\beta$-free languages} we mean the languages of \textit{all} Abelian-$\beta$-free words over a given alphabet. We consider three types of Abelian-power-free languages (weak, semistrong and strong). 

\section*{Results}

We prove uniform lower bounds for both strong and weak Abelian repetition threshold (denoted by $ART_s(k)$ and $ART_w(k)$, respectively). In view of the numerical results, it looks highly probable that our bound for $ART_s(k)$ is exact, while the bound for $ART_w(k)$ can be improved.

\smallskip
{\bf Theorem 1.}
$ART_{w}(k) \ge \frac{k}{k{-}2}$ for all $k \ge 10$.
\smallskip

{\bf Theorem 2.}
$ART_{s}(k) \ge \frac{k{-}2}{k{-}3}$ for all $k \ge 5$.
\smallskip

We use method proposed in \cite{Sh10tcs} to obtain upper bounds for the growth rates of certain Abelian power-free languages. These bounds provide a strong evidence that Abelian repetition thresholds for strong and semistrong Abelian powers coincide, so we are able to formulate the following

\smallskip
{\bf Conjecture 1.}
The Abelian repetition threshold for strong and semistrong Abelian powers is given by
\begin{equation*}
ART_{s}(k) = 
\begin{cases}
  11/3, & k = 2, \\
  2, & k = 3,\\
  9/5, & k = 4,\\
  (k{-}2)/(k{-}3), & k \ge 5.
\end{cases}
\end{equation*}

\begin{thebibliography}{99}

\begin{scriptsize}

\linespread{0.7}

\bibitem{ACR}
A. Aberkane, J. D. Currie, N. Rampersad, {\it The number of ternary words avoiding Abelian cubes grows exponentially}, 
J. Int. Seq., {\bf7} (2004), \#04.2.7, 13 pp. (electronic).

\bibitem {Bra}
F.-J. Brandenburg, {\it Uniformly growing $k$-th power free homomorphisms},
Theor. Comput. Sci., {\bf 23} (1983), 69-82.

\bibitem{Car}
A. Carpi, {\it On Dejean's conjecture over large alphabets}, Theor. Comput. Sci., {\bf 385} (2007), 137--151.

\bibitem{Car1}
A. Carpi, {\it On the number of Abelian square-free words on four letters}, Discr. Appl. Math., {\bf 81} (1998), 155--167.

\bibitem {CMR}
M. Crochemore, F. Mignosi, A. Restivo, {\it Automata and forbidden words}, Inform. Processing Letters, {\bf 67}(3) (1998), 111-117.

\bibitem{Cur}
J.\,D. Currie, {\it The number of binary words avoiding Abelian fourth powers grows exponentially}, Theor. Comput. Sci., {\bf319}(1--3) (2004), 441--446.

\bibitem {CR}
J.\,D. Currie, N. Rampersad, {\it A proof of Dejean's conjecture}, Math. Comp. {\bf80} (2011), 1063--1070.
%DOI: 10.1090/S0025-5718-2010-02407-X 

\bibitem {Dej}
F. Dejean, {\it Sur un Th\'eor\`eme de Thue}, J. Comb. Theory A {\bf13}(1) (1972), 90-99.

\bibitem {Dek}
F.\,M. Dekking, {\it Strongly non-repetitive sequences and progression-free sets}, J. Combin. Theory A {\bf27} (1979), 181-185.

\bibitem {Erd}
P. Erd\"os, {\it Some unsolved problems}, Magyar Tud. Akad. Mat. Kutat\'o Int. K\"ozl. {\bf6} (1961), 221--264.

\bibitem {Ker}
V. Ker\"anen, {\it Abelian squares are avoidable on 4 letters}, Proc. ICALP'92, 41--52. Springer, Berlin, 1992. (LNCS {\bf 623}).

\bibitem {Rao}
M. Rao, {\it Last Cases of Dejean's Conjecture}, Theor. Comput. Sci. {\bf 412} (2011), 3010--3018. Combinatorics on Words (WORDS 2009), 7th International Conference on Words.

\bibitem {Sh08ita}
A.M. Shur, {\it Comparing complexity functions of a language and its extendable part}, RAIRO Theor. Inf. Appl. {\bf42} (2008), 647--655.

\bibitem {Sh10tcs}
A.\,M. Shur, {\it Growth rates of complexity of power-free languages}, Theor. Comput. Sci. {\bf 411} (2010), 3209--3223.

\bibitem {Th}
A. Thue, {\it \"Uber unendliche Zeichenreihen}, Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl., Christiana {\bf 7} (1906), 1-22.

\end{scriptsize}

\end{thebibliography}

\end{document}


